The IP (Internet Protocol) Security (IPsec) standard, IP Security Internet Engineering Task Force (IETF) Request for Comments (RFC) 2401, published November 1998, is one method of protecting both the confidentiality and integrity of data transferred on a network. Cryptographic (crypto) information is contained in a data structure called a Security Association (SA). The information indicates to electronic systems utilizing IPsec how to perform crypto operations (e.g., encryption, decryption, authentication) on packets of network data. The crypto operations may be offloaded, where the packets of data are processed in hardware external to the system processor, to improve system performance.
A device driver is associated with the network interface hardware that couples the network traffic streams to an electronic system. The device driver that supports IPsec offload manages the SAs. For example, in a Network Driver Interface Specification (NDIS) environment, the miniport driver manages the SAs. In certain environments, the number of SAs to be managed can be very large. For example, in a server environment the number can reach many thousands. The driver maintains a pair of SAs for each connection, one for transmit and one for receive.
When a device driver receives a packet of network data in an environment supporting IPsec offload, the driver parses the packet to match the packet to its corresponding SA. The device driver searches an internal database of SAs to find which SA has a matching tuple. The IPsec standard specifies that the tuple uniquely identifies the SA for a data packet. However, in some IPSec implementations, such as the operating systems available from Microsoft Corporation, the receive SPI is guaranteed to be unique across the entire system. In this case, the SPI alone is sufficient to search for the SA, though the remaining members of the tuple must be verified as well.
In traditional NDIS implementations, the miniport driver maintains all SAs in one table. When the miniport needs to search the table for either transmit or receive packets, the miniport driver performs a linear search. This traditional approach has several inefficiencies. One shortfall is that a miniport driver searches receive SAs for transmit packets, and transmit SAs for receive packets. There is no chance of a match in either case. Another shortfall is that linear searches are inherently inefficient compared to other search algorithms, for example, binary searches.